1. Field of the Invention
The present invention is directed to indexing data within database management systems (DBMSs) and, more particularly, to a spatial quadtree index with cost-based query decomposition for queries against spatial data.
2. Background of the Invention
Relational database management systems (RDBMSs) are used to store many data types. Among the data types stored in RDBMSs are spatial data types that represent points, curves, lines (linestrings), surfaces, polygons, and collections thereof (i.e., multi-surface polygons and multi-curve linestrings). In order to improve query performance, database tables, including tables storing spatial data objects, in RDBMSs are often indexed.
There are two general types of RDBMS objects: data and queries. Quadtree indexes have been used for indexing spatial data within RDBMSs. Traditional techniques for creating quadtree indexes heuristically decompose both data objects and query objects. However the traditional technique for creating quadtree indexes for spatial indexing results in decomposing geometries into multiple entries in the index, and then uses an object decomposition algorithm.
A traditional approach to indexing spatial data is object decomposition. With the object decomposition approach each table row may generate multiple index rows (each is a Morton block). With object decomposition, each spatial object can be approximated by one or more quadtree blocks using a process known as tessellation. Given spatial object o, BLOCK(o) can denote the smallest quadtree block that completely covers o. A decomposition of o (with respect to a quadtree index) is a collection of objects {o1; . . . , on, n>1}, that satisfy the equation o=∪ioi and for all distinct pairs (oi; oj), BLOCK (oi) and BLOCK (oj) are disjoint. Traditional object decomposition can be applied in two distinct contexts: to data objects, and to query objects. Traditional algorithms for object decomposition choose a decomposition heuristically based only upon the geometry of the object itself (e.g. minimize the area of ∪i BLOCK(oi)). Accordingly, with traditional approaches to indexing spatial data using object decomposition, no distinction is made between data and query objects when performing the decomposition.
In existing RDBMSs, spatial indexes are created through object decomposition. However, each row of spatial data tables may generate multiple index rows, wherein each index row is a Morton block. This can result in up to O(2N) blocks for objects with N levels and 2N bits. With this conventional technique, each object is decomposed independently. This is can be inefficient because objects are decomposed before the DBMS knows the data distribution of the objects. When objects are decomposed independently tuning parameters specified by the user guide the depth of tiling for the objects. Conventional object decomposition also typically stores flags with the index entries. These flags may indicate properties such as whether an index entry touches, partly covers, or is within (i.e., in the interior) of an object. Although these flags can support a secondary filter, storing and maintaining the flags with the index entries creates additional overhead for an RDBMS and results in large index sizes
Accordingly, what is desired are systems, methods, and computer program products which create a spatial quadtree index with cost-based query decomposition in database management systems. What is further desired are systems, methods, and computer program products to efficiently create spatial quadtree indexes without decomposing objects and instead only decompose queries so as to avoid having to optimize each time a query is executed.